package class03;

/**
 * https://leetcode.com/problems/largest-bst-subtree
 * 可能性
 * 1. x 左子树的最远距离
 * 2. x 右子树的最远距离
 * 3. x 右子树的高度+x左子树高度+1
 * 递归的情况
 * 1. 左子树的最远距离和高度
 * 2. 右子树的最远距离和高度
 */
public class Code12_MaxDistance {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int value) {
            val = value;
        }
    }


    static class Info {
        int maxDistance;
        int height;

        Info(int height, int maxDistance) {
            this.height = height;
            this.maxDistance = maxDistance;
        }
    }


    static int maxSubBSTSize(TreeNode node) {
        return process(node).maxDistance;
    }

    static Info process(TreeNode node) {
        // base
        if (null == node) {
            return new Info(0, 0);
        }

        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);

        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        int mixDistance = Math.max(leftInfo.height, rightInfo.height) + 1;
        int maxDistance = Math.max(Math.max(leftInfo.maxDistance, rightInfo.maxDistance), mixDistance);
        return new Info(height, maxDistance);

    }

}
